package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1034 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int[][] colorBorder(int[][] grid, int row, int col, int color) {
            int[][] resGrid = new int[grid.length][grid[0].length];
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    resGrid[i][j] = grid[i][j];
                }
            }

            Deque<int[]> que = new LinkedList<>();
            que.push(new int[]{row, col});
            int componentColor = grid[row][col];

            while (!que.isEmpty()) {
                int[] cur = que.pollFirst();
                // 先判断当前点是否是边界
                if (cur[0] == 0 || cur[0] == grid.length - 1 || cur[1] == 0 || cur[1] == grid[0].length - 1) {
                    resGrid[cur[0]][cur[1]] = color;
                }

                // 颜色取负数防止重复遍历
                grid[cur[0]][cur[1]] *= -1;
                int sameColorCnt = 0;

                // 再检查四周的联通边界是否同色
                if (cur[0] > 0) {
                    if (grid[cur[0] - 1][cur[1]] == componentColor) {
                        que.push(new int[]{cur[0] - 1, cur[1]});
                    }
                    if (Math.abs(grid[cur[0] - 1][cur[1]]) == componentColor) {
                        sameColorCnt++;
                    }
                }

                if (cur[0] + 1 < grid.length) {
                    if (grid[cur[0] + 1][cur[1]] == componentColor) {
                        que.push(new int[]{cur[0] + 1, cur[1]});
                    }
                    if (Math.abs(grid[cur[0] + 1][cur[1]]) == componentColor) {
                        sameColorCnt++;
                    }
                }

                if (cur[1] > 0) {
                    if (grid[cur[0]][cur[1] - 1] == componentColor) {
                        que.push(new int[]{cur[0], cur[1] - 1});
                    }
                    if (Math.abs(grid[cur[0]][cur[1] - 1]) == componentColor) {
                        sameColorCnt++;
                    }
                }

                if (cur[1] + 1 < grid[0].length) {
                    if (grid[cur[0]][cur[1] + 1] == componentColor) {
                        que.push(new int[]{cur[0], cur[1] + 1});
                    }
                    if (Math.abs(grid[cur[0]][cur[1] + 1]) == componentColor) {
                        sameColorCnt++;
                    }
                }

                if (sameColorCnt < 4) {
                    resGrid[cur[0]][cur[1]] = color;
                }
            }

            return resGrid;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        int[][] arr = InputUtil.toDoubleIntegerArray("[[1,1],[1,2]]");
//        System.out.println(solution.colorBorder(arr, 0, 0, 3));

//        int[][] arr = InputUtil.toDoubleIntegerArray("[[1,2,2],[2,3,2]]");
//        System.out.println(solution.colorBorder(arr, 0, 1, 3));

//        int[][] arr = InputUtil.toDoubleIntegerArray("[[1,1,1],[1,1,1],[1,1,1]]");
//        System.out.println(solution.colorBorder(arr, 1, 1, 2));

        int[][] arr = InputUtil.toDoubleIntegerArray("[[1,2,1,2,1,2],[2,2,2,2,1,2],[1,2,2,2,1,2]]");
        System.out.println(solution.colorBorder(arr, 1, 3, 1));
    }

    public static void main(String[] args) throws Exception {
        LC1034 an = new LC1034();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
